# -*- coding: utf-8 -*-
# @Time    : 2020/11/8 20:03
# @Author  : DuJiabao
# @File    : TopologicalOrder.py
# @Description : 这是一个拓扑排序的程序

"""
综述：
拓扑排序，可实现先后优先级排序，代码实现原理如下：
        首先找出入度为0的顶点，进行删除，并对其指向的顶点，入度减1；
        如此反复，直到删除所有的顶点。
"""

class Node(object):
    def __init__(self, name):
        self.name = name
        self.next = None


class Queue(object):
    """
    这是一个基于链表的队列
    """
    def __init__(self):
        self.tail = Node(None)
        self.length = 0

    def __len__(self):
        return self.length

    def Enqueue(self, name):
        new = Node(name)
        new.next = self.tail.next
        self.tail.next = new
        self.length += 1

    def Dequeue(self):
        if self.tail.next is None:
            return False
        point = self.tail
        while point.next:
            prePoint = point
            point = point.next
        prePoint.next = None
        self.length -= 1
        return point


class Graph(object):
    """
    这是一个基于邻接表的有向图
    """

    def __init__(self):
        self.LinkList = {}
        self.indegree = {}
        self.order = []

    def __len__(self):
        return len(self.LinkList)

    def addUser(self, name):
        """
        增加用户
        :param name: 用户名
        :return: 无
        """
        if name not in self.LinkList:
            self.LinkList[name] = Node(None)
            self.indegree[name] = 0
            print(f"Add one user '{name}'")
        else:
            print("There is a name conflict! Please rename you nick name!")

    def addEdge(self, user1, user2):
        """
        有向边
        :param user1: 出发点
        :param user2: 终点
        :return: 无
        """
        if user1 not in self.LinkList:
            self.addUser(user1)
        if user2 not in self.LinkList:
            self.addUser(user2)
        point = self.LinkList[user1]
        while point.next:
            point = point.next
        point.next = Node(user2)
        self.indegree[user2] += 1

    def TopologicalOrder(self):
        """
        拓扑排序，可实现按照优先级，对图的顶点进行排序
        :return: 排序好的列表
        """
        queue = Queue()  # 利用队列的先进先出原理，按顺序保存入度为0的顶点
        # 遍历一遍，先把入度为0的顶点找出来
        for key, value in self.indegree.items():
            if value == 0:
                queue.Enqueue(key)
        # 若无入度为0的点，则表示这是一个有向有圈图，不可实现功能
        if len(queue) == 0:
            print("graph has a circle")
            return False
        # 循环，直到图的所有顶点都pop出来
        while len(self.LinkList) != 0:
            # 队列的所有内容均出队
            while len(queue) != 0:
                name = queue.Dequeue().name  # 出队
                self.order.append(name)  # 保存顺序
                point = self.LinkList[name]
                while point.next:
                    point = point.next
                    # 入度减1
                    self.indegree[point.name] -= 1
                # 删除已经出队的顶点
                self.LinkList.pop(name)
                self.indegree.pop(name)
            # 更新队列，将剩余入度为0的顶点入队
            for key, value in self.indegree.items():
                if value == 0:
                    queue.Enqueue(key)
        return self.order


if __name__ == '__main__':
    graph = Graph()
    graph.addEdge("v1", "v2")
    graph.addEdge("v1", "v3")
    graph.addEdge("v1", "v4")

    graph.addEdge("v2", "v4")
    graph.addEdge("v2", "v5")

    graph.addEdge("v3", "v6")

    graph.addEdge("v4", "v3")
    graph.addEdge("v4", "v6")
    graph.addEdge("v4", "v7")

    graph.addEdge("v5", "v4")
    graph.addEdge("v5", "v7")

    graph.addEdge("v7", "v6")

    print(graph.TopologicalOrder())
